#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "uthash.h"

/**
 * Definition for singly-linked list.
 */
struct ListNode {
	int val;
	struct ListNode* next;
};
typedef struct ListNode listNode, *listNode_ptr;

struct ListNode* sortList(struct ListNode* head);

int main()
{
	return 0;
}

struct ListNode* sortList(struct ListNode* head)
{
	int length = 0;
	listNode_ptr p = head;
	while (p) {
		length++;
		p = p->next;
	}

	listNode aux = { 0, head };
	for (int span = 1; span < length; span *= 2) {
		p = &aux;
		/* printf("aux.next:%d\t", aux.next->val); */
		for (int i = 0; i < length - span; i += span * 2) {
			listNode_ptr l2_aux = p, origin = p;
			for (int j = 0; j < span; j++)
				l2_aux = l2_aux->next;

			printf("span:%d\tp:%d\tl2:%d\n", span, p->val, l2_aux->val);

			for (int rightRest = span; rightRest > 0;) {
				listNode_ptr l1 = p->next,
							 l2 = l2_aux->next;
				int sub = l1->val - l2->val;

				if (sub > 0) {
					l2_aux->next = l2->next;
					l2->next = p->next;
					p->next = l2;
					rightRest--;
				}

				listNode_ptr bug = aux.next;
				while (bug) {
					printf("%d\t", bug->val);
					bug = bug->next;
				}
				putchar('\n');

				p = p->next;
				if (p == l2_aux || !l2_aux->next)
					break;
			}
			p = origin;
			for (int j = span * 2; j > 0 && p; j--) // 最后一轮循环中, p出现nullptr
				p = p->next;
		}
	}

	return aux.next;
}
